"""
假设密码长度 m，可使用大小写英文字母或数字
进行 n 次测试，每次测试会告知有 x[i] 个 char 可以匹配成功，有 y[i] 个 char 不但可以匹配成功，而且位置也正确
求满足要求的密码的数量

佬（叉呜呜）的解法：
记aₓᵧ为第x个位置是字母y。
那么你的约束就是
1.每个位置只有一个字母。(aₓᵧ对y求和为1)
2.字母只能存在和不存在(aₓᵧ为01变量)
3.一一配对约束。直接sum=x
4.位置不对约束。扣掉正确位置然后sum
"""
import numpy as np

n = 6
m = 3
k = 10


def main():
    # 用数组模拟一个真实密码
    password: list = np.random.randint(0, k, m).tolist()
    # 随机猜测的数字
    guesses = [np.random.randint(0, k, m).tolist() for _ in range(n)]
    xs = []
    ys = []
    # 生成输出
    print(rf'真实密码是 {password}')
    for guess in guesses:
        guess: list
        x = compare(password, guess)
        y = sum(p==q for p, q in zip(password, guess))
        print(rf'猜测密码 {guess}, 成功配对 {x} 个，其中 {y} 个位置正确')
        xs.append(x)
        ys.append(y)

    # 然后暴力穷举可能的数量
    test_ok = 0
    for i in range(k ** m):
        test_password = [i // k ** p % k for p in range(m)]
        for guess, x, y in zip(guesses, xs, ys):
            z = compare(guess, test_password)
            w = sum(p==q for p, q in zip(guess, test_password))
            if x != z or y != w:
                break
        else:
            print(rf'这个密码是可行的 {test_password}')
            test_ok += 1
        # print(test_password)
    print(rf'暴力穷举的可能的密码数量为 {test_ok}')

    # 然后设计算法求解可能的数量
    test_ok = resolve(guesses, xs, ys)
    print(rf'算法求解的可能的密码数量为 {test_ok}')


temp = np.zeros(k + 1, dtype=np.uint8)


def compare(g1, g2):
    global temp
    temp *= 0
    count = 0
    for u in g1:
        temp[u + 1] += 1
    for u in g2:
        if temp[u + 1] > 0:
            count += 1
            temp[u + 1] -= 1
    return count


def resolve(guesses, xs, ys):
    # 第一步，排除不存在的数字
    not_in = set()
    for guess, x, y in zip(guesses, xs, ys):
        if x == 0:
            for g in guess:
                not_in.add(g)
    # 第二步，穷举剩下的……
    test_ok = 0
    for i in range(k ** m):
        test_password = [i // k ** p % k for p in range(m)]
        if set(test_password) & not_in:
            continue
        for guess, x, y in zip(guesses, xs, ys):
            z = compare(guess, test_password)
            w = sum(p==q for p, q in zip(guess, test_password))
            if x != z or y != w:
                break
        else:
            print(rf'这个密码是可行的 {test_password}')
            test_ok += 1
        # print(test_password)
    return test_ok


if __name__ == '__main__':
    main()
